The present invention relates to flash memories and, more particularly, to a method of extending flash memory useful life by achieving wear leveling of the blocks in the memory.
Flash memory devices have been known for many years. Flash devices are used for manufacturing highly reliable solid-state disks, for data storage in PDAs and cellular phones, for audio files storage in MP3 players and for many other applications. One of the aspects that must be considered when designing a product using flash memory for data storage is that the number of times a flash block may be erased and re-written is limited. For example currently commercially-available NAND flash devices are typically specified by their manufacturers to support up to 100,000 cycles of write/erase per block, while the more dense Multi-Level-Cell (MLC) NAND flash devices storing two bits per cell are typically specified to support up to 10,000 cycles of write/erase per block. After a block reaches its specified write/erase cycles limit, it is no longer guaranteed by the device manufacturer to operate according to its specifications. Therefore, care must be taken to avoid a condition in which blocks of the memory unnecessarily reach this limit.
Because different flash memory vendors use different terminologies in describing the units of storage, we define here that for the purpose of the present disclosure a “block” is the smallest unit of storage that can be erased in a single operation, while a “page” is the smallest unit of storage that can be written (or “programmed”) in a single operation.
If no measures are taken to avoid non-even wear, the normal operation of a memory system might lead to such non-even wear across the population of blocks. This is because most software systems tend to write in a non-uniform manner across their storage address space. This is even more so when a file system such as Microsoft FAT is maintained in the storage system. In such cases some management data is typically kept by the file system at the beginning of the storage system address space. These data may be one or more copies of file allocation tables or the root directory of the storage volume. The frequency of writing to these management data areas is much higher than to other storage areas, and therefore, unless special measures are taken, the blocks containing them experience much higher numbers of write/erase cycles and reach their end of life sooner than other blocks. We then have a storage volume in which most blocks are still very far from their end-of-life limit but the volume as a whole already has reached its end-of-life because a few critical blocks already have reached that condition.
It is clear from the above that we should try to equalize the number of write/erase cycles across the blocks of the device. If all blocks have approximately similar write/erase histories, the life of the storage system as a whole is maximized.
The prior art teaches many solutions for solving the above flash memory wear-leveling problem. A few examples are:                U.S. Pat. No. 6,230,233 to Lofgren et al.        U.S. Pat. No. 5,341,339 to Wells        U.S. Pat. No. 5,568,423 to Jou et al.        U.S. Pat. No. 5,388,083 to Assar et al.        U.S. Pat. No. 5,712,819 to Harari        U.S. Pat. No. 6,570,790 to Harari        U.S. Pat. No. 5,963,480 to Harari        U.S. Pat. No. 6,831,865 to Chang et al.All of the above patents are incorporated by reference for all purposes as if fully set forth herein.        
What is common to all the above prior art is that it all is based on counting the number of erase cycles experienced by each block. For the purpose of the present disclosure an “erase count” is a number that represents the number of times a block of flash memory has been erased throughout its history of use. The erase counts are stored within the storage system and maintained during system operation. Whenever a block is erased, its erase count is incremented. Some of the above solutions store the erase count of a block within the block. Some store all erase counts of all blocks in a centralized table in a specially allocated location within the flash memory. Still others store the erase counts in the RAM of the controller managing the flash memory, in addition to storing the erase counts in non-volatile memory. But in all cases the number of erase cycles executed by a block is known and used for achieving the wear leveling goal. By looking at the erase counts of the blocks the flash management software can detect which blocks have been used the most and which blocks have been used the least.
There are two main levels in how this knowledge of the erase counts is put into use for achieving wear leveling. The simplest level is activated when a new block is needed to be allocated for use and the flash management system has to decide which one of the free blocks available for use should be the one allocated. Typically the decision algorithm prefers a block with a low number of erase cycles over another block with a high number of erase cycles, so that the spread of the counts will be smaller and the wear of the blocks will be more uniform. This level of wear leveling is herein called “dynamic wear leveling”. The more advanced level takes into account the fact that some files are static in nature and are typically written once and almost never updated or rewritten. This is the case with most operating system code files or software applications such as word processing programs. Without taking special measures, the wear leveling done by dynamic wear leveling algorithms does not affect the blocks used by static files, because those blocks never become free in the regular course of system operation. This leaves those blocks with very low erase counts and in practice means that the lifetime of the memory system is lower than it could have been. Therefore advanced wear leveling solutions handle this problem by occasionally forcing static files to move to other blocks even though these files are not rewritten. This allows blocks of static files to re-enter the pool of frequently allocated blocks that take part in allocations, and thus improves the overall leveling of the erase counts and consequently the lifetime of the storage system. This level of wear leveling is herein called “static wear leveling”. The term “wear leveling” with no additional qualification applies to both dynamic and static wear leveling.
The above prior art references disclose many algorithms that achieve the desired result of wear leveling, but all these algorithms rely on knowing the erase counts of the blocks.
An exception to this general rule is U.S. Pat. No. 6,732,221 to Ban. Ban discloses a method for achieving wear leveling in flash memory that does not rely on counting erase cycles per block. Instead Ban uses statistical methods to select the blocks to allocate and use, so that in the long run, after the system goes through many cycles of erasing blocks, the wear of all blocks is close to uniform with a high probability. However, Ban does not guarantee that the uniformity of wear leveling is achieved in the short term, after only a relatively low number of erase cycles. Therefore Ban's solution does not operate well for flash devices with a very low limit of write/erase cycles, such as 1,000.
In all the prior art solutions that rely on counting erase cycles per block, there is a need to store the count of each block. Whether the count is kept within the same block to which it applies or in any other location, storage must be allocated for the count. For a 100,000 cycles flash device at least 17 bits are needed per count, and for a 10,000 flash device at least 14 bits are needed per count. In some cases this is too much space to reserve for that purpose. For example, assume a flash management system for managing NAND flash devices such that each page of 512 bytes of user data are accompanied by 16 bytes of “extra area” for storing control information of the system. Because an erase count is an attribute of a full block and not of a single page, typically such an erase count is stored in only one of the pages of a block, typically in the first page. So at least three bytes (assuming a 100,000 cycles device) of the extra area of the first page should be allocated to storing the erase count of the block. But these extra area bytes might be needed for storing other management information required by the flash management software for efficient management, or for parity bits of an error correction scheme for the data stored in the page.
Similarly, if the erase counts are kept in a central table, the amount of space required might be too high. If a flash disk contains four 1 Gbit flash devices, each having 4,096 blocks of 32Kbytes, and each requiring an erase count of three bytes, then the size of the table is 4×4,096×3=49,152 bytes. This is more than the size of a block, even before including multiple copies for backup. More importantly, it is useful for performance reasons to keep a copy of the erase counts table in RAM, but the above amount is too large, typically beyond the amount of available RAM in flash controllers.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method for achieving wear leveling of flash memory blocks that on the one hand provides uniform erase cycles across the blocks population while on the other hand consumes less memory than the prior art methods that count the erase cycles and store their number.